package chapter03_binaryTree;

import java.util.HashMap;

/**
 * 描述：先序、中序、后序两两结合重构二叉树
 *      给定三种遍历方式的数组，任意两种方式组合重构二叉树
 *
 *      通过两种方式的遍历数组，锁定左右子树的下标范围，有中序遍历的序列的情况都可以准确地区分左右子树的下标边界，
 *      但如果没有中序遍历，仅靠先序和后序是无法确定左右子树边界，
 *
 *
 * @author hl
 * @date 2021/6/2 9:47
 */
public class TowOrderReconTree {
    /**
     * 先序中序重构二叉树
     * 通过先序数组的将中序数组划分出左右子树部分
     * 先序数组的第一个是头结点，而在中序数组中找出头结点的位置，然后头结点左边的结点是左子树，右边的结点是右子树，重复这个过程
     * 在中序遍历中找到子树头结点的可以哈希表进行加速
     * @param pre
     * @param in
     * @return
     */
    public Node preInToTree(int[] pre, int[] in){
        HashMap<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            inMap.put(in[i], i);
        }
        return preIn(pre, 0, pre.length - 1, in,0, in.length - 1, inMap);
    }
    private Node preIn(int[] pre, int ps, int pe,  int[] in, int is, int ie, HashMap<Integer, Integer> inMap) {
        if (ps > pe) {
            return null;
        }
        Node head = new Node(pre[ps]);
        int index = inMap.get(pre[ps]);
        head.left = preIn(pre, ps + 1, ps + index - is, in,  is, index - 1, inMap);
        head.right = preIn(pre, ps + index -is + 1, pe,  in, index + 1, ie, inMap);
        return head;
    }

    /**
     * 中序后序构建二叉树
     * 跟先序中序构建类似，不过是用后序数组来划分中序数组
     * @param in
     * @param pos
     * @return
     */
    public Node InPosToTree(int[] in, int[] pos){
        HashMap<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            inMap.put(in[i], i);
        }
        return inPos(in, 0, in.length - 1, pos, 0, pos.length - 1, inMap);
    }

    private Node inPos(int[] in, int is, int ie, int[] pos, int ps, int pe, HashMap<Integer, Integer> inMap) {
        if (ps > pe) {
            return null;
        }
        Node head = new Node(pos[pe]);
        int index = inMap.get(pos[pe]);
        head.left = inPos(in, is, index - 1, pos, ps, ps + index - is - 1, inMap);
        head.right = inPos(in, index + 1, ie, pos, ps + index - is, pe - 1, inMap);
        return head;
    }

    /**
     * 先序后序构建二叉树
     *  通过先后序后序遍历数组只能确定子树的头结点，而无法确定子树的左右子树分界的范围，
     *          比如后序遍历23，只能确定3是根结点而无法确定2是左孩子还是右孩子
     *          比如前序遍历12，只能确定1是根结点而无法确定2是左孩子还是右孩子
     *          如果有中序遍历就可以准确地对左右子树的边界进行区分
     *   因此，如果要通过先序后序遍历重建二叉树，那么原始二叉树的除了叶子结点外所有结点都的有左孩子和右孩子，否则不能准确的构建
     * @return
     */
    public Node prePosToTree(int[] pre, int[] pos){
        HashMap<Integer, Integer> posMap = new HashMap<>();
        for (int i = 0; i < pos.length; i++) {
            posMap.put(pos[i], i);
        }
        return prePos(pre, 0, pre.length - 1, pos, 0, pos.length - 1, posMap);
    }


    private Node prePos(int[] pre, int pi, int pj, int[] s, int si, int sj, HashMap<Integer, Integer> posMap) {
        Node head = new Node(s[sj--]);
        if (pi == pj) {
            return null;
        }
        //默认pi + 1是左子树的头结点，实际上左子树可能为空，pi + 1 是右子树的头结点
        int index = posMap.get(pre[++pi]);
        head.left = prePos(pre, pi, pi + index - si, s, si, index - 1, posMap);
        head.right = prePos(pre, pi + index - si + 1, pj, s, index + 1, sj, posMap);
        return head;
    }

}
